/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/word-search
   @Language: C++
   @Datetime: 19-07-08 11:07
   */

class Solution {
	bool backtrack(vector<vector<char>>& board, string &word, 
			int r, int c, int pos, unordered_set<long> &visit){
		if(pos==word.length()) return true;
		if(r<0||r>=board.size()||c<0||c>=board[0].size()) return false;
		const long cell=((r+0L)<<32)|c;
		if(visit.count(cell)||board[r][c]!=word[pos]) return false;
		visit.insert(cell);
		const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
		for(int i=0; i<4; ++i)
			if(backtrack(board,word,r+dir[i][0],c+dir[i][1],pos+1,visit)) return true;
		visit.erase(cell);
		return false;
	}
public:
	bool exist(vector<vector<char>>& board, string &word) {
		for(int i=0; i<board.size(); ++i)
			for(int j=0; j<board[i].size(); ++j)
				if(board[i][j]==word[0]){
					unordered_set<long> visit;
					if(backtrack(board,word,i,j,0,visit)) return true;
				}
		return false;
	}
};

